Mobile telecommunications units (MUs) such as cell phones and other related devices are now commonplace in our culture. Historically, MUs have typically been treated as a movable version of a standard telephone. In particular, a main object of current systems has been to hide the fact that the user of the MU is in fact mobile by providing a standard telephone number for reaching the MU regardless of location. Thus, MUs are typically used in a manner so as to conceal the location of the mobile user to make it appear to the outside world that the unit is a traditional stationary unit (SU). Similarly, when telecommunication system users place phone calls using MUs, they dial traditional telephone numbers as if they were in their home location, making call placement appear to users of MUs as if they were in their home cities, regardless of their actual location.
FCC Wireless Requirements
A wireless phone is a valuable emergency tool that can be taken almost anywhere. For many Americans, the ability to call for help in an emergency is the principal reason they own a wireless phone. But that help may never arrive, or may be too late, if the 911 call does not get through or if emergency response teams cannot locate the user quickly. In a series of orders since 1996, the Federal Communications Commission (FCC) has taken action to improve the quality and reliability of 911 emergency services for wireless phone users, by adopting rules to govern the availability of basic 911 services and the implementation of enhanced 911 (E911) for wireless services. The E911 rules seek to improve the reliability of wireless 911 services and to provide emergency services personnel with location information that will enable these emergency services personnel to locate and assist wireless 911 callers. The E911 rules require that wireless carriers deliver 911 calls and implement the technology that provides the 911 emergency call response center with information about the caller's location.
The approximate location of an MU is always known to a telecommunication infrastructure in the form of which cell base station the MU is communicating with (e.g., as taught in U.S. Pat. No. 6,061,561). A prime motivation for being able to access such information is to determine the location of MU users who place calls to Emergency-911 call centers or are otherwise in distress. In order to improve the effectiveness of Emergency-911 services in particular, more accurate position information is being made available via the telecommunication infrastructure. For example, U.S. Pat. No. 6,067,045 teaches the use of combining Global Positioning System (GPS) information with a telecommunication infrastructure to accurately determine the position of an MU, whereas U.S. Pat. No. 6,055,434 teaches the use of low powered beacons scattered throughout MU usage areas. Regardless of the technology used, the end result is that telecommunication systems are rapidly being provided with an ability to accurately determine the geographic location of an individual MU. The advent of precise location information for MUs has made possible new services dependent on a known location of a MU.
The availability of position information with respect to MU users makes location-based services (LBS) possible. Examples of location-based services include nearest friend finder and dating applications, nearest restaurant finder applications and advertisements that are delivered to MUs when the MU is in a particular location. These services are known, respectively, as mobile to mobile applications, mobile to static applications, and static to mobile applications.
Virtually all location-based services that exist today are designed to provide a mobile user with information relative to a point of interest (“POI”) or a static location. For example, a mobile user may request the location of movie theaters or restaurants proximate to him, even within his zip code. ZIP code level locating capability has typically been used in the mobile environment because it is often the only information the user may have available. Additionally, ZIP code level positioning is made available automatically through networks such as PalmNet.
Fine grain locating capability is available in the US mainly through on-the-fly geocoding of street address. Companies such as MapQuest exemplify this technique. A drawback to this technique is that it requires the user to manually enter his or her street address into the MU. Automatic locating capability is currently available in Japan, Europe, and soon will be available in the US as a result of the FCC-E911 mandate. Precise location will become a commodity and a wealth of mobile applications will seek to build services based on that attribute.
Precise and frequent knowledge of a mobile unit's (“MU”) location will enable a new generation of mobile service: mobile unit to mobile unit. This knowledge will additionally allow improved versions of mobile unit to stationary unit services. An MU-to-MU service seeks to identify groups of proximate users, formed dynamically, using location and profile information as criteria. For example, consider a business networking service that would allow a salesman at a tradeshow to locate and get in touch with potential clients and leads. Or consider a static to mobile application such as a proximity-based advertising engine that publishes location-based promotions to nearby subscribers.
As devices become capable of supporting applications such as interactive proximity based wireless chat, people finder and/or messaging, the value of location in determining the location of friends and consumers will increase. Location will become critical in creating the “network effect” whereby messages are automatically initiated between proximate users and service providers.
ZIP code based POI locating, as is known in the art, can be performed with a traditional Relational Database Management System (“RDBMS”). A standard Structured Query Language (“SQL”) query searches the database for entries with the requested ZIP code. At no time is the distance from the mobile user to the point of interest actually computed. Therefore, ZIP based MU-to-POI applications are trivial to implement.
At a finer granularity level, geocoding can be performed on a database to associate each entry with a latitude and longitude. If the user's latitude and longitude is known, the closest POI can be determined by a brute force search (“within distance query”). The distance to every POI can be approximated by treating the local area as a flat X-Y grid and calculating SQRT (ΔX2+ΔY2) for each POI. While the simulation can be performed for a few users, scaling to one million users would involve at least ten million floating-point operations per within distance query. This technique quickly becomes far too computation-intensive to work on a database with any more than a handful of geocoded entries.
An accepted technique for overcoming this challenge is to perform a tessellation on the spatial database after the data has been bulk loaded into the database. The process of tessellating a database, i.e. overlaying logical tiles on the data, can be a challenging endeavor. For example, a poorly tuned tessellation would create fixed sized tiles. Each region is divided into an even number of fixed sized tiles that cover the possible range of geographic coordinates. For a static dataset (such as geocoded yellow page business listings), it is possible to know the extent of the region a priori. For example, a geocoded yellow page business listing database for a particular city might specify extents of [−122.2, −123.0] [37.0, 37.8]. Additionally, tiles are created even where there is no data within the tile.
After the initial bulk load of data, an index is created to allow the tile of any point to be determined quickly. Consider the case where one wants to find all points within 0.7 degrees of [122.223, 37.056]. The exact within distance querying algorithms will vary by implementation. However, the process for performing a within distance query typically begins with finding a starting tile in the index, then searching within the tile. Consulting the index, we begin by searching all points in tile 1, then expanding our search to adjacent tiles whose bounds fall at least partially within the search radius. If each tile contains a relatively small number of points, and the search radius is small, the within distance computation will be performed only on a small subset of the database.
With geocoded data loaded in bulk, it is possible to “tune” the database for higher performance. In areas with high point density, tiles can be recursively tessellated. This places fewer points per tile and results in faster queries if the query radius falls inside a tile. Therefore, fast queries can only be guaranteed if the database is properly tessellated. Typically, proper tessellation involves running tuning scripts to determine the optimal tessellation level, and requires the data to be precisely indexed. Record insertions must then update the index making it an expensive process. In addition, the coordinate extents must be known in advance to ensure that all inserted records fall inside a tile.
If (1) the data is bulk loaded initially, (2) the database is well-tuned, and (3) there are few transactional inserts, then a tessellated database can provide high performance for a static dataset. Databases such as Oracle Spatial and Informix Spatial, using R-Tree indices, can quickly perform a within distance query on a geocoded yellow page database, if properly tuned by a database administrator (“DBA”). However, performance immediately becomes unacceptable when data is transitionally loaded (e.g. location data continuously being updated) and the coordinate extents are unknown, for example in the case where there exist unlimited or very large geographic boundaries within which a mobile unit might be located.
Consider a scenario in which a tessellated spatial database using an R-Tree index attempts to store the real-time locations of millions of mobile users. A number of inefficiencies will be encountered:
Unknown Extents: For a small-scale local service it may be possible to set the coordinate extents to a square surrounding a city. For a scaleable system that can service users in any nation or on any scale, the extents must be set to cover the entire surface of the earth as any user can potentially log in from anywhere (Japan, Sweden, etc.). Therefore, either the extents are set to cover the latitude and longitude of the entire earth, or multiple database instances must be used, each covering separate extents. This is clearly an unacceptable solution given the overhead and costs associated with database hardware and administration.
Poor Tessellation: In order to achieve high computing performance, the spatial database must be tuned before it is accessed. In this instance, and while many parameters must also be tuned, we focus on tuning as principally involving the determining parameters such as the tessellation level. Tuning is only possible if the locations of point data are known at the time of tuning. Clearly, the locations of MUs cannot be known before the MUs log in and update their position. Therefore, tessellation level optimization will not be possible and many, if not most, tiles will cover unpopulated areas. Similarly, in densely populated areas there will be too many users per tile.
Not Adaptive: Because the locations of users will constantly shift, an adaptive scheme would have to re-tessellate the database on the fly. This solution is an expensive operation and would have to be performed often to maintain any form of consistency with actual user locations.
Expensive Transactions: Every time a MUs position changes, the database index must be rebuilt, regardless of whether or not any re-tessellation is performed.
Degradation: In a database that is not properly implemented for moving point data, performance degradation will occur as a function of the number of transactions, the number of rows, and data distribution.
The key reason for the existence of such problems is that traditional spatial databases are not optimized for moving point data. Thus, it would be an improvement in the art to provide a database that can effectively and efficiently manage moving point data representing large numbers of users.